<head>
    <meta charset="UTF-8">
<title>算法提高 Trade on Verweggistan</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>问题描述<br />
自从Peter Stuyvesant和Abel Tasman的日子以后，荷兰商人已经周游世界来买卖商品。有一次在Verweggistan的贸易，但是它在很短的时间后就结束了。在读完这个故事之后你就明白了。<br />
在当时Verweggistan是非常受欢迎的，因为世界上只有那个地方的人知道怎样制作一个&ldquo;prul&rdquo;（或者&ldquo;prullen&rdquo;，荷兰语中的复数形式），并且如今只有很少的人知道什么是一个&ldquo;prul&rdquo;。<br />
&ldquo;prul&rdquo;是在工场里生产的。当一个&ldquo;prul&rdquo;做完的时候，它被包装在一个箱子里，然后放在之前生产的&ldquo;prul&rdquo;所装的箱子堆的上面。<br />
价格取决于生产&ldquo;prul&rdquo;所需要的时间。如果一切顺利，一个&ldquo;prul&rdquo;的价格会是1或者2弗罗林，但是在一个恶劣的日子，价格会很容易地上升到15弗罗林或者更高。&ldquo;prul&rdquo;在品质上没有什么差别，所有的&ldquo;prul&rdquo;具有相同的价值。<br />
在这些天，&ldquo;prul&rdquo;在荷兰的售价为每件10弗罗林。交通运输的费用是可以忽略的，因为&ldquo;prul&rdquo;无论如何都会作为额外的东西被装载到要航行的船上。当一个荷兰商人去Verweggistan时，他有一个明确的目的：买&ldquo;prul&rdquo;，在荷兰销售，并且最大化他的利润。不幸的是，Verweggistan地区对&ldquo;prul&rdquo;的交易方式使得这比某些人预想的更为复杂。<br />
有人认为这很简单，商人会买那些最便宜的&ldquo;prul&rdquo;，而那些售价比10弗罗林高的&ldquo;prul&rdquo;会一直不能出售。不幸的是，Verweggistan的所有工场按照一种奇怪的顺序销售&ldquo;prul&rdquo;。堆顶的箱子里的&ldquo;prul&rdquo;会最先销售，然后销售从顶上开始数的第二个箱子里的&ldquo;prul&rdquo;，以此类推。所以即使第五个箱子里的&ldquo;prul&rdquo;是最便宜的，商人也必须买它上面四个箱子里的&ldquo;prul&rdquo;才能得到它。<br />
正如你想象的那样，这使得商人通过购买正确的&ldquo;prul&rdquo;的组合来最大化他们的利润是相当难的。没有电脑帮助他们的优化，他们迅速彻底失去了交易&ldquo;prul&rdquo;的兴趣。<br />
在这个问题中，给你对几个工场里箱子堆的描述。你必须根据上面所给的限制，计算出一个商人通过购买箱子堆中的&ldquo;prul&rdquo;可以获得的最大利润。另外，你必须确定他需要买多少个&ldquo;prul&rdquo;才能获得最大利润。<br />
输入格式<br />
输入文件包含多组测试数据。每个测试数据的第一行是一个整数w(1&lt;=w&lt;=50)，该测试数据中工场的数目。<br />
接下来有w行，每行描述一个放&ldquo;prul&rdquo;的箱子堆。每行的第一个整数b(0&lt;=b&lt;=20)，表示堆中的箱子数。接下来是b个正整数，表示堆中&ldquo;prul&rdquo;的价格（单位为弗罗林）。输入中箱子的顺序是从顶到底。<br />
输入数据终止于w=0，不再有后续的描述内容。<br />
输出格式<br />
对于每组测试数据，输出测试点的编号(1,2...)。然后输出两行，第一行输出商人可以获得的最大利润。第二行输出为获得最大利润商人需要买的&ldquo;prul&rdquo;数量。如果这个数量不是唯一确定的，按照升序输出可能的值。如果有超过10种可能的取值，只输出10个最小的取值。<br />
样例输入<br />
1<br />
6 12 3 10 7 16 5<br />
2<br />
5 7 3 11 9 10<br />
9 1 2 3 4 10 16 10 4 16<br />
0<br />
样例输出<br />
Workyards 1<br />
Maximum profit is 8.<br />
Number of pruls to buy: 4<br />
Workyards 2<br />
Maximum profit is 40.<br />
Number of pruls to buy: 6 7 8 9 10 12 13<br />
数据规模和约定<br />
1&lt;=w&lt;=50，0&lt;=b&lt;=20，输入文件保证测试点个数不超过10。</p>